//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_FINEGRAINEDLOCKLIST_H
#define HYDRA_FINEGRAINEDLOCKLIST_H 1

#include "hydra/allocators/BasicAllocator.h"
#include "hydra/locks/TTASLock.h"

namespace Hydra
{
	/**
	 * A list using fine-grained locking. Each node is locked individually, allowing multiple threads to
	 * traverse and manipulate the list in parallel.
	 *
	 * Iterator can only move forward. Must have a temporary lifetime, a stored Iterator will block all other
	 * Iterators from passing it. Most FineGrainedLockList methods use Iterators internally, so do not call these
	 * methods while another Iterator exists.
	 *
	 * Only operations on the front of the list are supported, there is no pushBack(), back(), popBack() methods.
	 * Locks must be acquired in front to back order, otherwise we will have deadlocks, so operations on the back
	 * of the list would require a full list traversal to acquire the correct locks.
	 *
	 * Elements are returned by value only, returning by reference is not safe as another list could delete the element.
	 */
	template<typename T, typename Allocator=BasicAllocator, typename Lock=TTASLock>
	class FineGrainedLockList
	{
	private:
		struct Node
		{
			T m_item;
			Atomic<Node*> m_next;	//atomic only so that isEmpty does not need to acquire a lock, hopefully being atomic won't penalize other functions
			Lock m_lock;
		};

	public:
		/**
		 * Use this Iterator with extreme care, the lock based nature of the list means that Iterators cannot pass
		 * each other, so they can deadlock. A good rule of thumb is to never have more than one Iterator instance
		 * at a time in each thread. Also remember that many of the functions in FineGrainedLockList will use an
		 * Iterator internally.
		 */
		class Iterator
		{
			friend class FineGrainedLockList;
		public:
			///Creates an Iterator which points to the start of the list
			Iterator(FineGrainedLockList& list) : m_list(list)
			{
				m_pred = &list.m_head;
				m_pred->m_lock.lock();
				m_curr = m_pred->m_next;
				m_curr->m_lock.lock();
			}
			~Iterator()
			{
				m_pred->m_lock.unlock();
				m_curr->m_lock.unlock();
			}
			///Returns the item currently pointed to by the Iterator and steps the Iterator to the next item in the list
			const T next()
			{
				assert(hasNext());
				T value = m_curr->m_item;
				m_pred->m_lock.unlock();
				m_pred = m_curr;
				m_curr = m_curr->m_next;
				m_curr->m_lock.lock();
				return value;
			}
			///Returns the item currently pointed to by the Iterator, without stepping forward
			const T peekNext()
			{
				assert(hasNext());
				return m_curr->m_item;
			}
			///Returns false if the Iterator is at the end of the list
			bool hasNext() const
			{
				return (m_curr->m_next != NULL);
			}
			///Sets the item currently pointed to by the Iterator, most containers cannot support this operation safely but this one can because the item is locked
			void setValue(const T& item)
			{
				assert(hasNext());
				m_curr->m_item = item;
			}
			void toFront()
			{
				m_pred->m_lock.unlock();
				m_curr->m_lock.unlock();

				m_pred = &m_list.m_head;
				m_pred->m_lock.lock();
				m_curr = m_pred->m_next;
				m_curr->m_lock.lock();
			}
		private:
			FineGrainedLockList& m_list;
			Node* m_pred;
			Node* m_curr;
		};

		FineGrainedLockList()
		{
			m_head.m_next = &m_alloc.m_tail;
			m_alloc.m_tail.m_next = NULL;
		}

		~FineGrainedLockList()
		{
			//no need to lock here, if more than one thread is calling the destructor we have bigger problems
			Node* node = m_head.m_next;
			Node* nextNode = node->m_next;
			while( nextNode )
			{
				freeNode(node);
				node = nextNode;
				nextNode = node->m_next;
			}
		}

		void pushFront(const T& item)
		{
			//only necessary to lock head, no need to lock the next node since we never read from it
			m_head.m_lock.lock();

			Node* newNode = allocNode();
			newNode->m_item = item;
			newNode->m_next = m_head.m_next;
			m_head.m_next = newNode;

			m_head.m_lock.unlock();
		}

		bool front(T& item)
		{
			//need to lock head and next, to ensure node is not deleted while we are reading it
			m_head.m_lock.lock();
			Node* node = m_head.m_next;
			node->m_lock.lock();

			bool isFound = false;
			if( node->m_next )
			{
				item = node->m_item;
				isFound = true;
			}

			m_head.m_lock.unlock();
			node->m_lock.unlock();

			return isFound;
		}

		bool popFront(T& item)
		{
			m_head.m_lock.lock();
			Node* node = m_head.m_next;
			node->m_lock.lock();
			bool isFound = false;
			if( node->m_next )
			{
				item = node->m_item;
				m_head.m_next = node->m_next;
				isFound = true;
			}
			m_head.m_lock.unlock();
			node->m_lock.unlock();
			if( isFound )
				freeNode(node);
			return isFound;
		}

		/**
		 * Inserts the new item before the item currently pointed to by the Iterator. The Iterator will
		 * be pointing to the new item after this function.
		 */
		void insert(Iterator& iter, const T& item)
		{
			Node* newNode = allocNode();
			newNode->m_item = item;
			newNode->m_next = iter.m_curr;
			iter.m_pred->m_next = newNode;
			iter.m_curr->m_lock.unlock();
			iter.m_curr = newNode;
			iter.m_curr->m_lock.lock();
		}

		///Tests if the specified item is contained in the list, uses operator== to compare.
		bool contains(const T& item)
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				T cmpItem = iter.next();
				if( cmpItem == item )
					return true;
			}
			return false;
		}

		///Removes the item pointed to by iter, after removal the Iterator will be pointing to the next item in the list.
		void remove(Iterator& iter)
		{
			Node* newNext = iter.m_curr->m_next;
			iter.m_pred->m_next = newNext;
			iter.m_curr->m_lock.unlock();
			freeNode(iter.m_curr);
			iter.m_curr = newNext;
			iter.m_curr->m_lock.lock();
		}

		///Removes the first occurrence of item from the list, uses operator== to compare.
		bool remove(const T& item)
		{
			Node* removedNode = NULL;
			{
				Iterator iter(*this);
				while( iter.hasNext() )
				{
					if( iter.peekNext() == item )
					{
						//a little tricky here, the Iterator will be invalid after removing m_curr from the list, but its
						// destructor will still do the right thing and release its locks
						iter.m_pred->m_next = iter.m_curr->m_next;
						removedNode = iter.m_curr;
						break;
					}
					iter.next();
				}
			}
			if( removedNode )
			{
				//can now delete the node, the Iterator has been destroyed and has released its lock
				freeNode(removedNode);
				return true;
			}
			return false;
		}

		///Removes all occurrences of item from the list, uses operator== to compare.
		void removeAll(const T& item)
		{
			Iterator iter(*this);
			while( iter.hasNext() )
			{
				if( iter.peekNext() == item )
					remove(iter);
				else
					iter.next();
			}
		}

		bool isEmpty()
		{
			//no need to lock, m_next is Atomic just for this function's benefit
			return (m_head.m_next == &m_alloc.m_tail);
		}

		///Removes all items from the list, note that this is not fast as it acquires locks on every item.
		void clear()
		{
			Iterator iter(*this);
			while( iter.hasNext() )
				remove(iter);
		}

	private:
		Node* allocNode()
		{
			Node* node = reinterpret_cast<Node*>(m_alloc.alloc(sizeof(Node)));
			new(node) Node;
			return node;
		}
		void freeNode(Node* node)
		{
			node->~Node();
			m_alloc.free(node);
		}

		struct AllocAndTail : public Allocator
		{
			Node m_tail;
		};
		Node m_head;
		AllocAndTail m_alloc;
	};
}

#endif
